SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>FOSD program cubes</title>

</head>

FOSD program cubes

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

In <a href="Feature-oriented_software_development" class="mw-redirect" title="Feature-oriented software development">feature-oriented software development</a>, feature-oriented software development program cubes (FOSD program cubes) are n-dimensional arrays of functions (program transformations) that represent n-dimensional product lines. A program is a composition of features: a base program is augmented with increments in program functionality, called features, to produce a complex program. A <a href="Software_product_line" title="Software product line">software product line</a> (SPL) is a family of related programs. A typical product line has F0 as a base program, and F1..Fn as features that could be added to F0. Different compositions of features yield different programs.

Let + denote the feature composition operation. A program P in SPL might have the following expression:

That is, P extends program F0 with features F1, F2, F4, and F8 in this order.

We can recast P in terms of a projection and contraction of a 1-dimensional array.

Let Fi = [F0 .. Fn] denote the array of features used by a product line. A projection of Fi eliminates

unneeded features, yielding a shorter array (call it) Gi. A contraction of Gi sums each Gi in a specific order, to yield a scalar expression. The expression for P becomes:

</mrow>

</munder>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P=\sum _{i=(0,1,2,4,8)}\mathbf {F} _{i}}</annotation>

</semantics>

</math><img src="./b693450af7ef6d837b7395920046ea3e4cf5c09a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:16.778ex; height:6.009ex;" alt="{\displaystyle P=\sum _{i=(0,1,2,4,8)}\mathbf {F} _{i}}" loading="lazy"></dd></dl>

where the index values accomplish projection and summation is array contraction. This idea

generalizes to n-dimensional arrays that model multi-dimensional product lines.

<div class="mw-heading mw-heading2"><h2 id="Multi-dimensional_product_lines">Multi-dimensional product lines</h2></div>

A multi-dimensional product line is described by multiple interacting sets of features.<a href="#cite_note-origami-1">[1]</a>

As an elementary 2D example, it is easy to create a product line of calculators, where

variants offer different sets of operations. Another variation

might offer different presentation front ends to calculators, one with no GUI, another

with a Java GUI, a third with a web GUI. These variations interact:

each GUI representation references a specific calculator operation, so each GUI

feature cannot be designed independently of its

calculator feature. Such a design leads to a matrix: columns represent increments in

calculator functionality, and rows represent different presentation front-ends. Such a matrix M is shown to the right: columns allow one to pair

basic calculator functionality (base) with optional logarithmic/exponentiation (lx)

and trigonometric (td) features. Rows allow one to pair core functionality with no

front-end (core), with optional GUI (gui) and web-based (web) front-ends.

An element Mij implements the interaction of column feature i and row feature j.

For example, the element labeled cb is a base program that implements the core functionality of a calculator. Element gb adds code that displays the core functionality as a GUI; element wb adds code that displays the core functionality via the web. Similarly, element ct adds trigonometric code to the core calculator functionality; elements gt and wt add code to display the trigonometric functionality as a GUI and web front-ends.

A calculator is uniquely specified by two sequences of features: one sequence defines the calculator functionality, the other the front-end.

For example, calculator C that offers both base and trig functionality in a web format

is defined by the expression:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</munder>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C=M_{cb}+M_{ct}+M_{wb}+M_{wt}=\sum _{i=(core,web) \atop j=(base,td)}\mathbf {M} _{ij}}</annotation>

</semantics>

</math><img src="./df63ee12383418f55061909b98ced9d5fe07e802.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.005ex; width:45.272ex; height:7.509ex;" alt="{\displaystyle C=M_{cb}+M_{ct}+M_{wb}+M_{wt}=\sum _{i=(core,web) \atop j=(base,td)}\mathbf {M} _{ij}}" loading="lazy"></dd></dl>

<dl><dd>Note: Each dimension is a collection of base programs and features. Not all of their compositions are meaningful. A <a href="Feature_Model" class="mw-redirect" title="Feature Model">feature model</a> defines the legal combinations of features. Thus, each dimension would have its own feature model. It is possible that selected features along one dimension may preclude or require features along other dimensions. In any case, these feature models define the legal combinations of features in a multidimensional product line.</dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Cubes">Cubes</h2></div>

In general, a cube is an n-dimensional array. The rank of a cube is its dimensionality.

A scalar is a cube of rank 0, a vector is a cube of rank 1, and a matrix is

rank 2. Following tensor notation: the number of indices a cube has designates

its rank. A scalar S is rank 0 (it has no indices), Vk is a vector (rank

1), Mij is a matrix (rank 2), Cijk is a cube (rank 3).

Program Cubes are n-dimensional arrays of functions

(program transformations) that represent n-dimensional product lines.

The values along each axis

of a cube denote either a base program or a feature that could elaborate a base program.

The rank of a product line is the rank of its cube.

<dl><dd>Note: program cubes are inspired by <a href="Tensor" title="Tensor">tensors</a> and <a href="OLAP_cube" title="OLAP cube">data cubes</a> in databases. The primary difference is that data cube elements are numerical values that are added during cube contraction; program cube elements are transformations that are composed. Both use <a href="Tensor" title="Tensor">tensor</a> notations and terminology.</dd></dl>

A program in an n-dimensional SPL is uniquely specified by n sequences of features S1..Sn, one per dimension.

The design of a program is a scalar (expression) that is formed by (1) projecting the cube

of its unneeded elements, and (2) contracting the resultant kcube to a scalar:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P=\sum _{i_{1}=S_{1}\dots i_{n}=S_{n}}\mathbf {K} _{i_{1}\dots i_{n}}}</annotation>

</semantics>

</math><img src="./95eff0b944b688a46efd05e28a220eb474255f91.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:23.64ex; height:5.843ex;" alt="{\displaystyle P=\sum _{i_{1}=S_{1}\dots i_{n}=S_{n}}\mathbf {K} _{i_{1}\dots i_{n}}}" loading="lazy"></dd></dl>

Program generation is evaluating the scalar expression to produce program P.

An interesting property of cube design is that the order in which dimensions are contracted does not

matter—any permutation of dimensions during contraction results in a different

scalar expression (i.e. a different program design), but all expressions produce the

same value (program). For example, another expression (design) to produce calculator C contracts

dimensions in the opposite order from its original specification:

Or more generally:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P=\sum _{i_{n}=S_{n}\dots i_{1}=S_{1}}\mathbf {K} _{i_{1}\dots i_{n}}}</annotation>

</semantics>

</math><img src="./a1fe709c2e4c73e0ff39da25ced1bb27bfecc3a9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:23.64ex; height:5.843ex;" alt="{\displaystyle P=\sum _{i_{n}=S_{n}\dots i_{1}=S_{1}}\mathbf {K} _{i_{1}\dots i_{n}}}" loading="lazy"></dd></dl>

<dl><dd>Note: Underlying cube designs is a <a href="Commutative_diagram" title="Commutative diagram">commutative diagram</a>, such that there are an exponential number of paths from the empty program 0 to program P. Each path denotes a particular contraction of a cube, and corresponds to a unique incremental design of P. Included among these paths are cube aggregations that contract cubes using different dimensional orders.</dd></dl>

The significance of program cubes is that it provides a structured way in which to

express and build multi-dimensional models of SPLs. Further, it provides scalable

specifications. If each dimension has k values, an n-cube specification of a program

requires O(kn) terms, as opposed to O(kn) cube elements that would otherwise

have to be identified and then composed. In general, cubes provide a compact way

to specify complex programs.

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

The <a href="Expression_problem" title="Expression problem">expression problem</a> (a.k.a. the 'extensibility problem) is a fundamental problem in programming languages aimed at type systems that can add new classes and methods to a program in a type-safe manner.<a href="#cite_note-Reynolds-5">[5]</a><a href="#cite_note-Cook-6">[6]</a><a href="#cite_note-Wadler-7">[7]</a><a href="#cite_note-Synth-8">[8]</a>

It is also a fundamental problem in multi-dimensional SPL design. The expression problem is an example of an SPL of rank 2. The following applications either explain/illustrate the expression problem or show how it scales to product lines of large programs. EP is really a SPL of ~30 line programs; the applications below show how these ideas scale to programs of >30K lines (a 103 increase in size).

<ul><li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20170706122152/ftp://ftp.cs.utexas.edu/pub/predator/ECOOP2005.pdf">Expression Problem</a></li>

<li><a rel="nofollow" class="external text" href="http://www.cs.utexas.edu/users/schwartz/ATS/EPL/index.html">Illustration of Small Expression Problem</a></li>

<li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20170706014148/ftp://ftp.cs.utexas.edu/pub/predator/Origami.pdf">Extensible IDEs</a></li>

<li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20170706014145/ftp://ftp.cs.utexas.edu/pub/predator/OrigamiMDSC.pdf">Multi-Dimensional Separation of Concerns</a></li>

<li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20170706122700/ftp://ftp.cs.utexas.edu/pub/predator/TSE-AHEAD.pdf">Calculator Product Line</a></li></ul>

Also, <a href="FOSD_metamodels" title="FOSD metamodels">FOSD metamodels</a> can be viewed as special cases of program cubes.

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20170706014148/ftp://ftp.cs.utexas.edu/pub/predator/Origami.pdf">"Generating Product-Lines of Product-Families"</a> (PDF). Archived from <a rel="nofollow" class="external text" href="ftp://ftp.cs.utexas.edu/pub/predator/Origami.pdf">the original</a> (PDF) on 2017-07-06.</cite>

</li>

<li id="cite_note-sigsoft03-2"><a href="#cite_ref-sigsoft03_2-0">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20170706014145/ftp://ftp.cs.utexas.edu/pub/predator/OrigamiMDSC.pdf">"Refinements and Multi-Dimensional Separation of Concerns"</a> (PDF). Archived from <a rel="nofollow" class="external text" href="ftp://ftp.cs.utexas.edu/pub/predator/OrigamiMDSC.pdf">the original</a> (PDF) on 2017-07-06.</cite>

</li>

<li id="cite_note-ahead-3"><a href="#cite_ref-ahead_3-0">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20170706122700/ftp://ftp.cs.utexas.edu/pub/predator/TSE-AHEAD.pdf">"Scaling Step-Wise Refinement"</a> (PDF). Archived from <a rel="nofollow" class="external text" href="ftp://ftp.cs.utexas.edu/pub/predator/TSE-AHEAD.pdf">the original</a> (PDF) on 2017-07-06.</cite>

</li>

<li id="cite_note-ECOOP05-4"><a href="#cite_ref-ECOOP05_4-0">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20170706122152/ftp://ftp.cs.utexas.edu/pub/predator/ECOOP2005.pdf">"Evaluating Support for Features in Advanced Modularization Technologies"</a> (PDF). Archived from <a rel="nofollow" class="external text" href="ftp://ftp.cs.utexas.edu/pub/predator/ECOOP2005.pdf">the original</a> (PDF) on 2017-07-06.</cite>

</li>

<cite class="citation book cs1"><a rel="nofollow" class="external text" href="http://portal.acm.org/citation.cfm?id=186680">User-defined types and procedural data structures as complementary approaches to data abstraction</a>. MIT Press. 12 August 1994. pp. 13–23. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780262071550</bdi>.</cite>

</li>

<cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.cs.utexas.edu/users/wcook/papers/OOPvsADT/CookOOPvsADT90.pdf">"Object-Oriented Programming versues Abstract Data Types"</a> (PDF).</cite>

</li>

<cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.daimi.au.dk/~madst/tool/papers/expression.txt">"The Expression Problem"</a>.</cite>

</li>

<cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://citeseer.ist.psu.edu/krishnamurthi98synthesizing.html">"Synthesizing Object-Oriented and Functional Design to Promote Re-Use"</a>.</cite>

</li>

</ol></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-05-27" href="https://en.wikipedia.org/wiki/?title=FOSD_program_cubes&oldid=1292519519">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>